// Package coding_round_1 10——912
// @Title coding_round_1
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/4 11:13
// @Create  2021/9/4 11:13
package coding_round_1

// 选择排序
func SortArray(nums []int) []int {
	if nums == nil || len(nums) < 1 {
		return nil
	}
	for i := 0; i < len(nums); i++ {
		minIndex := i
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[minIndex] {
				minIndex = j
			}
		}
		if i != minIndex {
			nums[minIndex], nums[i] = nums[i], nums[minIndex]
		}
	}
	return nums
}

// 冒泡排序
func SortArrayBubble(nums []int) []int {
	if nums == nil || len(nums) < 1 {
		return nil
	}
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] > nums[j] {
				nums[i], nums[j] = nums[j], nums[i]
			}
		}
	}
	return nums
}

// 插入排序
func SortArrayInsert(nums []int) []int {
	if nums == nil || len(nums) < 1 {
		return nil
	}

	return nums
}

func quickSort(nums []int, l int, r int) {
	if l >= r {
		return
	}

	index := l - 1
	for i := l; i <= r; i++ {
		if nums[i] < nums[r] {
			index++
			nums[index], nums[i] = nums[i], nums[index]
		}
	}

	nums[index+1], nums[r] = nums[r], nums[index+1]

	quickSort(nums, l, index)
	quickSort(nums, index+2, r)
}

// 快速排序
func SortArrayQuick(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	quickSort(nums, 0, len(nums)-1)
	return nums
}

// 归并排序

func merge(left []int, right []int) []int {
	index := 0
	leftIndex := 0
	rightIndex := 0
	newArr := make([]int, len(left)+len(right))

	for leftIndex < len(left) && rightIndex < len(right) {
		if left[leftIndex] < right[rightIndex] {
			newArr[index] = left[leftIndex]
			index++
			leftIndex++
		} else {
			newArr[index] = right[rightIndex]
			index++
			rightIndex++
		}
	}

	for leftIndex < len(left) {
		newArr[index] = left[leftIndex]
		index++
		leftIndex++
	}

	for rightIndex < len(right) {
		newArr[index] = right[rightIndex]
		index++
		rightIndex++
	}

	return newArr
}
func SortArrayMerge(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}

	mid := len(nums) >> 1
	left := nums[:mid]
	right := nums[mid:len(nums)]

	return merge(SortArrayMerge(left), SortArrayMerge(right))
}

// 堆排序

func maxHeap(nums []int, length int) {
	for i := len(nums)>>1 - 1; i >= 0; i-- {
		heapify(nums, i, length)
	}
}

func heapify(nums []int, i int, len int) {
	left := 2*i + 1
	right := 2*i + 2
	large := i

	if left <= len && nums[left] > nums[large] {
		large = left
	}

	if right <= len && nums[right] > nums[large] {
		large = right
	}

	if large != i {
		nums[large], nums[i] = nums[i], nums[large]
		heapify(nums, large, len)
	}
}

func SortArrayHeap(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	maxHeap(nums, len(nums)-1)
	for i := len(nums) - 1; i >= 0; i-- {
		nums[i], nums[0] = nums[0], nums[i]
		heapify(nums[:i], 0, len(nums[:i])-1)
	}
	return nums
}
